/*
 * @lc app=leetcode.cn id=235 lang=cpp
 *
 * [235] 二叉搜索树的最近公共祖先
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
  {
    if (nullptr == root) return nullptr;  // 空结点时返回空

    // 从根节点开始递归
    if (root->val > max(p->val, q->val))  // 如果p,q在当前结点左子树，则对左子树遍历
      return lowestCommonAncestor(root->left, p, q);

    else if (root->val < min(p->val, q->val))  // 如果p,q在当前结点右子树，则对右子树遍历
    {
      return lowestCommonAncestor(root->right, p, q);
    }

    else  // 包含等于最小值最大值的情况，如果当前结点在p,q之间，则为最低公共父结点（因为从上往下在遍历，故遇到的第一个满足此条件的就是）
    {
      return root;
    }
  }
};
// @lc code=end
